package com.mango.data.structure.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 实现堆
 *
 * @Author: mango
 * @Date: 2022/4/30 2:24 下午
 */
public class Heap<T extends Comparable> {
    // 集合，存数据的
    private List<T> data;
    // 堆大小
    private int size;
    // 比较器
    private Comparator<T> comparator;

    public Heap() {
        this.data = new ArrayList<>();
        this.size = 0;
        this.comparator = null;
    }

    public Heap(Comparator<T> comparator) {
        this.data = new ArrayList<>();
        this.size = 0;
        this.comparator = comparator;
    }

    /**
     * 判断栈是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

    private void swap(int i, int j) {
        T temp = this.data.get(i);
        this.data.set(i, this.data.get(j));
        this.data.set(j, temp);
    }

    /**
     * 加入元素到栈
     *
     * @param t
     */
    public void insert(T t) {
        this.data.add(t);
        int index = this.size;
        // 向上堆化
        while (index>0 && this.compare(index,(index-1)/2)) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
        this.size++;
    }

    private boolean compare(int i,int j){
        if(null == comparator){
            return this.data.get(i).compareTo(this.data.get(j)) < 0 ? true : false;
        }else{
            return comparator.compare(this.data.get(i),this.data.get(j)) < 0 ? true : false;
        }
    }

    /**
     * 弹出栈顶元素
     *
     * @return
     */
    public T pop() {
        // 取栈顶0位置
        T result = this.data.get(0);
        swap(0, this.size-1);
        this.data.set(this.size-1,null);
        this.size--;
        heapfiy(0, this.size);
        return result;
    }

    /**
     * 向下堆化
     * @param index 起始下标
     * @param size  堆大小
     */
    public void heapfiy(int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int the = left + 1 < size && this.compare(left+1,left) ? left + 1 : left;
            the = this.compare(the,index) ? the : index;
            if (the == index) {
                break;
            }
            swap(the, index);
            index = the;
            left = index * 2 + 1;
        }
    }

    public static void main(String[] args) {
        Heap<Integer> heap = new Heap<>(((o1, o2) -> o2 - o1));
        heap.insert(1);
        heap.insert(6);
        heap.insert(5);
        heap.insert(9);
        heap.insert(2);
        heap.insert(33);

        while (!heap.isEmpty()){
            System.out.println(heap.pop());
        }
    }
}
